package 代码随想录_动态规划.背包_01;

/**
 * @author zx
 * @create 2022-05-30 15:08
 * 1.确定dp数组（dp table）以及下标的含义
 *  dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。
 * 2.确定递推公式
 *  dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
 * 3.dp数组如何初始化
 * 因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。
 * 而要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。
 * dp[j]都初始化为0
 * 4.确定遍历顺序
 *
 * 5.举例推导dp数组
 * 分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
 * 在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
 * 那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
 */
public class 最后一块石头的重量II_1049 {
    /**
     * @return (题型三)：求背包最多能装多少重量
     */
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int i = 0;i < stones.length;i++){
            sum += stones[i];
        }
        int[] dp = new int[sum / 2 + 1];
        //dp[j]表示容量(其实就是重量)为j的背包,最多可以背dp[j]这么重的石头.
        for(int i = 0;i < stones.length;i++){
            for(int j = sum / 2;j >= stones[i];j--){
                dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
            }
        }
        int target = sum / 2;
        return sum - dp[target] - dp[target];
    }
}
